Find elements in a contaminated binary tree [DFS]¶
Time: O(N); Space: O(H); medium
Given a binary tree with the following rules:
root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2
Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.
You need to first recover the binary tree and then implement the FindElements class:
FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.
Example 1:
Input/Output:
root = {TreeNode} [-1,null,-1]
f = FindElements(root)
f.find(1) -> False
f.find(2) -> True
Example 2:
Input/Output:
root = {TreeNode} [-1,-1,-1,-1,-1]
f = FindElements(root)
f.find(1) -> True
f.find(3) -> True
f.find(5) -> False
Example 3:
Input/Output:
root = {TreeNode} [-1,null,-1,-1,null,-1]
f = FindElements(root)
f.find(2) -> True
f.find(3) -> False
f.find(4) -> False
f.find(5) -> True
Constraints:
TreeNode.val == -1
The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6
Hints:
Use DFS to traverse the binary tree and recover it.
Use a hashset to store TreeNode.val for finding.
[25]:
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
1. Depth First Search¶
[26]:
class FindElements(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
def dfs(node, v, lookup):
if not node:
return
node.val = v
lookup.add(v)
dfs(node.left, 2 * v + 1, lookup)
dfs(node.right, 2 * v + 2, lookup)
self.__lookup = set()
dfs(root, 0, self.__lookup)
def find(self, target):
"""
:type target: int
:rtype: bool
"""
return target in self.__lookup
[27]:
root = TreeNode(-1)
root.right = TreeNode(-1)
tree = FindElements(root)
assert tree.find(1) == False
assert tree.find(2) == True
[28]:
root = TreeNode(-1)
root.left, root.right = TreeNode(-1), TreeNode(-1)
root.left.left, root.left.right = TreeNode(-1), TreeNode(-1)
tree = FindElements(root)
assert tree.find(1) == True
assert tree.find(3) == True
assert tree.find(5) == False
[29]:
root = TreeNode(-1)
root.right = TreeNode(-1)
root.right.left = TreeNode(-1)
root.right.left.left = TreeNode(-1)
tree = FindElements(root)
assert tree.find(2) == True
assert tree.find(3) == False
assert tree.find(4) == False
assert tree.find(5) == True